#include <iostream>
#include <utility>

template <class K> class hash; // define a class before explicit specialization

template<>
class hash<std::string>
{
public:
    size_t operator[] (const std::string theKey)const
    {
        unsigned long hashValue = 0;
        int length = (int)theKey.length();
        for(int i = 0; i < length; ++i){
            hashValue = 5 * hashValue + theKey.at(i);
        }

        return size_t(hashValue);
    }
};

template <>
class hash<int>
{
public:
    size_t operator[](const int theKey)const
    {
        return size_t(theKey);
    }
};

template<>
class hash<long>
{
public:
    size_t operator[](const long theKey)const
    {
        return size_t(theKey);
    }
};


template<class K, class E>
class HashTable
{
private:
    std::pair<const K, E> ** m_table; // the table to restore pair
    hash<K> m_hash; // map the key to unique unsigned long type
    int m_size; // the number of pair
    int m_divisor; // the bin of table

public:
    HashTable(int theDivisior)
    {
        m_divisor = theDivisior;
        m_size = 0;

        m_table = new std::pair<const K,E>* [m_divisor];
        for(int i = 0; i < m_divisor; ++i){
            m_table[i] = nullptr;
        }
    }
    ~HashTable()
    {
        delete [] m_table;
    }

    int searsh(const K& theKey)const
    {
        int i = static_cast<int>(m_hash[theKey] % m_divisor);
        int j = i;
        do{
            if(m_table[j] == nullptr || m_table[j]->first == theKey){
                return j;
            }
            j = (j + 1) % m_divisor; // 循环线性表
        }while(i == j);

        return j;
    }

    std::pair<const K, E>* find(const K& theKey)const
    {
        int i = searsh(theKey);
        if(m_table[i]->first == theKey){
            return m_table[i];
        }else{
            return nullptr;
        }
    }

    void insert(const std::pair<const K, E>& thePair)
    {
        int i = searsh(thePair.first);
        // 如果不存在，则添加
        if(m_table[i] == nullptr){
            m_table[i] = new std::pair<const K, E>(thePair);
            m_size ++;
        }else if(m_table[i]->first == thePair.first){
            // 如果重复，则替换
            m_table[i]->second = thePair.second;
        }
    }
};




int main(int argc, char *argv[])
{
    int divisor = 10;
    HashTable<int, int> hash_table(divisor);

    for(int i = 0; i < divisor; ++i){
        const std::pair<const int, int> a(i, 10 * i);
        hash_table.insert(a);
    }

    std::cout<<hash_table.find(4)->second<<std::endl;

    std::cout<<hash_table.searsh(6)<<std::endl;

    std::cout<<hash_table.find(11)<<std::endl;

    return 0;
}











